Search for: All records

The separability of clusters is one of the most desired properties in clustering. There is a wide range of settings in which different clusterings of the same data set appear. We are interested in applications for which there is a need for an explicit, gradual transition of one separable clustering into another one. This transition should be a sequence of simple, natural steps that upholds separability of the clusters throughout. We design an algorithm for such a transition. We exploit the intimate connection of separability and linear programming over bounded-shape partition and transportation polytopes: separable clusterings lie on the boundary of partition polytopes and form a subset of the vertices of the corresponding transportation polytopes, and circuits of both polytopes are readily interpreted as sequential or cyclical exchanges of items between clusters. This allows for a natural approach to achieve the desired transition through a combination of two walks: an edge walk between two so-called radial clusterings in a transportation polytope, computed through an adaptation of classical tools of sensitivity analysis and parametric programming, and a walk from a separable clustering to a corresponding radial clustering, computed through a tailored, iterative routine updating cluster sizes and reoptimizing the cluster assignment of items. Funding: Borgwardt gratefully acknowledges support of this work through National Science Foundation [Grant 2006183] Circuit Walks in Optimization, Algorithmic Foundations, Division of Computing and Communication Foundations; through Air Force Office of Scientific Research [Grant FA9550-21-1-0233] The Hirsch Conjecture for Totally-Unimodular Polyhedra; and through Simons Collaboration [Grant 524210] Polyhedral Theory in Data Analytics. Happach has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. 

We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of min sum set cover, several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the min sum ordering problem (MSOP), which generalizes all these problems using a cost and a weight function defined on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time [Formula: see text]-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results. Summary of Contribution: This paper provides a general framework for min sum ordering problems. Within the realm of theoretical computer science, these problems include min sum set cover and its generalizations, as well as problems in Boolean function evaluation. On the operations research side, they include problems in search theory and scheduling. We present and analyze a very general algorithm for these problems, unifying several previous results on various min sum ordering problems and resulting in new constant factor guarantees for others. 

We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of Min Sum Set Cover (MSSC), several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the Min Sum Ordering Problem (MSOP) which generalizes all these problems using a cost and a weight function on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time 4α-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results.